Many data processing systems, including communication systems, receive, process and transmit relatively large quantities of data in a relatively short period of time. Such systems use data handling functions or schemes to manage or control a massive amount of data flow often divided into data packets. Further, such data processing systems often provide various common services to multiple data sources or service requesters.
Hardware and software limitations prevent systems from processing and transmitting data as fast as it is received. As a result, data processing systems and communication systems use data handling schemes to place restrictions on or regulate the flow of input data to accommodate the system's processing and transmission rates and to achieve an optimal data flow rate within the system.
Conventional data handling schemes incorporate a compromise that attempts to allocate an amount of system time and resources for servicing each service requester based on the requester's individual needs. During each service requester's allotted time, that requester is provided full use of system resources, such as data transfer, bus communication, data transmission and the like. Outside of the requester's allocated time, the requester may be provided with a minimal portion of the system's resources, such as buffered memory for storing input data from the service requester.
In conventional data processing systems and communication systems, data handling schemes are configured to provide system services for requesters that send data packets at a rate or frequency that is controlled by the requester. This situation can present these systems with a wide range of input data rates that desirably need to be accommodated. In an attempt to optimize data flow within these systems, conventional data handling schemes use various methods.
One simple method is herein referred to as a round robin method. The round robin method assigns a service number to each requester and then goes sequentially from a minimum service number to a maximum service number, checking to see if the requester at that service number is requesting service. This method gives each requester an equal opportunity to obtain system services. Unfortunately, the round robin method does not balance service among the requesters. Accordingly, requesters requiring more frequent servicing, such as those requesters with relatively high input data rates, have no more opportunity to obtain service than requesters requiring less frequent servicing. Furthermore, the round robin method typically cannot guarantee service to these high rate requesters.
Another method, hard priority, assigns a priority to each requester in accordance with the requester's input data rate. Requesters having high input data rates are assigned high priority and requesters having low input data rates are assigned low priority. The requester with the highest priority will receive service whenever it requests service. Lower priority requesters receive service only when higher priority requesters are not requesting service. If one or more requesters have a relatively high priority and one requester has a relatively low priority, the requester with the low priority may have to wait an undesirable length of time before being serviced and may possibly not get serviced at all. This method tends to over-service higher priority requesters and causes lower priority requesters to be starved for service. In addition, the hard priority method requires more buffer memory than the round robin method since data from low priority requesters must be stored while high priority requesters are serviced, and the lowest priority requester typically cannot be guaranteed of receiving service.
A soft priority method, uses a relatively large memory buffers to temporarily hold data packets from the requesters being serviced. Data packets in the buffer are routed out of the buffers according to a first-in-first-out (FIFO) priority scheme. This method uses packet depth in the buffer to initiate a variable priority scheme. That is, the buffer is examined and data packet routing is prioritized according to which requesters have the most amount of data packets in the buffer. For example, a requester having 100 data packets in the buffer will have its data packets routed out of the buffer before a requester having 2 data packets in the buffer. The soft priority method uses relatively large buffers which are expensive, increase system power requirements and reduce system reliability. Moreover, the soft priority method increases transport delay between data packet arrival and data packet servicing, which is undesirable for real time applications such as communication systems.
The above discussed and other data handling methods fail to provide for a balance in service when service requesters have divergent input data rates. This typically results in a build up of data packets causing undesirable and/or unacceptable delays in data transmission. For a communication system transmitting voice data between two phone users, a delay of several data packets may cause such a large delay in a conversation that the communication is unacceptable.
Accordingly a need exists for an improved method to schedule allocation of system services in common use by multiple service requesters within a data processing system.